Models, Algorithms, and Technologies for Network Analysis by Boris Goldengorin Valery A. Kalyagin & Panos M. Pardalos

Author:Boris Goldengorin, Valery A. Kalyagin & Panos M. Pardalos
Language: eng
Format: epub
Publisher: Springer New York, New York, NY

After the root finds and , a subgraph is formed by removing all vertices in and , along with all associated edges. All the nodes from both sets can move and will become descendants of at least one node in according to the algorithms described below.

4.1 Optimal Algorithm

For a root to achieve an optimal achievable topology, it essentially has to consider all possible tree topologies and select the final topology based on the achievable tree that gives the minimum aggregate data traffic. In this section, we provide details about how the optimal solution can be found, subject to the constraint that the topology is reorganized around a preselected root. We use the branch-and-bound technique to limit the complexity of this combinatorial search.

As described above, the root first obtains the active and passive moving node sets using Algorithm 2, as well as the subgraph of nonmoving nodes. A brute-force solution is for the root to consider all nodes in the active moving node set and to evaluate the aggregate data traffic for all achievable tree topologies such that . All achievable tree topologies can be achieved by applying the concept of Prufer code sequence [1, 21]. Each unique Prufer code sequence can be used to represent unique spanning trees. Each unique tree topology with n-labeled nodes can be encoded to obtain a unique Prufer code sequence p of length n − 2, where each element in p is obtained from the set of n node labels. Likewise, each unique Prufer code sequence p of length n − 2 can be decoded to obtain unique tree topology with n labeled nodes. Hence, there exits n n − 2 unique Prufer code sequences p of length n − 2 that can be decoded to obtain n n − 2 unique tree topologies with n label nodes and vice versa.

To obtain all achievable tree topologies such that , subgraph is first contracted into a single node . A set containing all possible Prufer sequences p is then generated from a set of nodes including , , and . Each unique tree topology can be obtained by decoding each . Still more than one possible unique tree for each Prufer sequence may exist since a node always contained in has to be extracted as subgraph to achieve at least one unique graph .

To achieve all unique tree topologies from each , an edge set that contains the edges that are incident to in is first considered. Here v denotes a root of subtree and therefore is connected to in by its associated edge . Hence, the number of subtrees connected to in is given by . To form a unique spanning tree, each has to be attached to at least one node of a subgraph obtained from extracting a node by connecting a root of each to any node , where denotes a set of node of the subgraph . Hence, there are unique tree topologies that can be obtained from each Prufer sequence since there are possible ways to attach all subtrees to .

The

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.